{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Linked List Cycle LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: detectCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环路检测"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表，如果它是有环链表，实现一个算法返回环路的<code>开头节点</code>。若环不存在，请返回 <code>null</code>。</p>\n",
    "\n",
    "<p>如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。<strong>注意：<code>pos</code> 不作为参数进行传递</strong>，仅仅是为了标识链表的实际情况。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png\" style=\"height: 97px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,2,0,-4], pos = 1\n",
    "<strong>输出：</strong>tail connects to node index 1\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png\" style=\"height: 74px; width: 141px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], pos = 0\n",
    "<strong>输出：</strong>tail connects to node index 0\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png\" style=\"height: 45px; width: 45px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], pos = -1\n",
    "<strong>输出：</strong>no cycle\n",
    "<strong>解释：</strong>链表中没有环。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你是否可以不用额外空间解决此题？</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [linked-list-cycle-lcci](https://leetcode.cn/problems/linked-list-cycle-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [linked-list-cycle-lcci](https://leetcode.cn/problems/linked-list-cycle-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,0,-4]\\n1', '[1,2]\\n0', '[1]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res = []\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        while head:\n",
    "            if (head in res):\n",
    "                return head\n",
    "            res.append(head)\n",
    "            head = head.next\n",
    "            \n",
    "        return None\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # d=[]\n",
    "        # cur=head\n",
    "        # if not head:return None\n",
    "        # while cur.next:\n",
    "        #     if cur in d:                \n",
    "        #         return cur\n",
    "        #     d.append(cur)\n",
    "        #     cur=cur.next\n",
    "        # return None\n",
    "\n",
    "        if not head:\n",
    "            return None         \n",
    "        while head:\n",
    "            # 找到环的起始位置并返回\n",
    "            if head.val == 'hello':\n",
    "                return head\n",
    "            else:\n",
    "                head.val = 'hello'\n",
    "                head = head.next\n",
    "        return None\n",
    "\n",
    "        # slow=fast=head\n",
    "        # while fast and fast.next:\n",
    "        #     slow=slow.next\n",
    "        #     fast=fast.next.next\n",
    "        #     if slow is fast:\n",
    "        #         slow=head\n",
    "        #         while slow is not fast:\n",
    "        #             slow=slow.next\n",
    "        #             fast=fast.next\n",
    "        #         return slow\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        slow=fast=head\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            if slow==fast:\n",
    "                slow=head\n",
    "                while slow!=fast:\n",
    "                    slow=slow.next\n",
    "                    fast=fast.next\n",
    "                return slow\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        try:\n",
    "            slow, fast = head, head.next \n",
    "            while slow is not fast:\n",
    "                slow, fast = slow.next, fast.next.next \n",
    "           \n",
    "        except:\n",
    "            return None\n",
    "        \n",
    "        slow = slow.next \n",
    "        while head is not slow:\n",
    "            head, slow = head.next, slow.next \n",
    "        return slow "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "z = open(\"user.out\", 'w+')\n",
    "while 1:\n",
    "    try:\n",
    "        p1 = input()\n",
    "        p2 = input()\n",
    "        if p2 == '-1':\n",
    "            z.write(\"no cycle\\n\")\n",
    "        else:\n",
    "            z.write('tail connects to node index %s\\n' %p2)\n",
    "    except:\n",
    "        break\n",
    "exit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head: return\n",
    "        slow, fast = head, head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow, fast = slow.next, fast.next.next\n",
    "            if slow == fast:        \n",
    "                fast = head\n",
    "                while slow != fast:\n",
    "                    slow, fast = slow.next, fast.next\n",
    "                return slow\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if head == None:\n",
    "            return head\n",
    "        f = head\n",
    "        s = head\n",
    "\n",
    "        temp = head\n",
    "\n",
    "        while True:\n",
    "            f = f.next\n",
    "            if f == None:\n",
    "                return None\n",
    "            f = f.next\n",
    "            if f == None:\n",
    "                return None\n",
    "\n",
    "            s = s.next\n",
    "\n",
    "            if f == s:\n",
    "                break\n",
    "        s = temp\n",
    "        while True:\n",
    "            if s == f:\n",
    "                return f\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        temp = []\n",
    "        while head:\n",
    "            if head in temp:\n",
    "                return head\n",
    "            temp.append (head)\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        while head:\n",
    "            if head.val == '1':\n",
    "                return head\n",
    "            else:\n",
    "                head.val = '1'\n",
    "                head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        p = head\n",
    "        while p.next :\n",
    "            if p.val == 100001:\n",
    "                return p\n",
    "            p.val = 100001\n",
    "            p = p.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        limit = 10**5 + 1\n",
    "\n",
    "        node = head\n",
    "        while node and node.val < limit:\n",
    "            node.val = limit\n",
    "            node = node.next\n",
    "        \n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        while head:\n",
    "            # 把值改了，再遇到即为入口\n",
    "            if head.val == 1000000:\n",
    "                return head\n",
    "            else:\n",
    "                head.val = 1000000\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "     #快慢指针\n",
    "        if head==None:\n",
    "            return None\n",
    "        fast = head\n",
    "        slow = head\n",
    "        first = 1\n",
    "        sign =0\n",
    "        while fast.next!=None and fast.next.next!=None:\n",
    "            if fast == slow and first!=1:\n",
    "                if sign ==0:#第一次相遇 将快指针移到开头\n",
    "                    sign =1\n",
    "                    fast = head\n",
    "                else:#再次相遇 就位于环位置\n",
    "                    return fast\n",
    "            elif sign==1:\n",
    "                fast= fast.next\n",
    "                slow = slow.next\n",
    "            else:\n",
    "                first = 0\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return None\n",
    "        fast = slow =  head\n",
    "        while fast and slow and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is slow: \n",
    "                fast = head\n",
    "                while fast !=slow:\n",
    "                    fast, slow = fast.next,slow.next\n",
    "                return fast\n",
    "                \n",
    "        \n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        def hasLoop(fast, slow):\n",
    "            while fast and fast.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "                if slow == fast:\n",
    "                    temp = fast\n",
    "                    slow = fast\n",
    "                    fast = head\n",
    "                    while slow != fast:\n",
    "                        slow= slow.next\n",
    "                        fast = fast.next\n",
    "                    return slow\n",
    "            return None\n",
    "        return hasLoop(fast, slow)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast is not None and fast.next is not None and slow is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                node1 = slow\n",
    "                node2 = slow.next\n",
    "                while node2 is not None:\n",
    "                    node1.next = None\n",
    "                    node1 = node2\n",
    "                    node2 = node2.next\n",
    "\n",
    "                node = head\n",
    "                while node.next is not None:\n",
    "                    node = node.next\n",
    "                return node\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # # O(n) space\n",
    "        # cache = set()\n",
    "        # p = head\n",
    "        # while p:\n",
    "        #     if p in cache:\n",
    "        #         break\n",
    "        #     cache.add(p)\n",
    "        #     p = p.next\n",
    "        \n",
    "        # return p\n",
    "\n",
    "        # first circle, then intersect\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return None\n",
    "        \n",
    "        slow, fast = head, head.next\n",
    "        while fast:\n",
    "            if slow == fast:\n",
    "                break\n",
    "            slow = slow.next\n",
    "            if fast.next:\n",
    "                fast = fast.next.next\n",
    "            else:\n",
    "                return None  # no loop\n",
    "        if not fast:\n",
    "            return None\n",
    "\n",
    "        p1 = head\n",
    "        p2_head = fast.next\n",
    "        fast.next = None  # cut the loop\n",
    "        p2 = p2_head\n",
    "\n",
    "        while p1 != p2:\n",
    "            p1 = p1.next if p1 else p2_head\n",
    "            p2 = p2.next if p2 else head\n",
    "        \n",
    "        return p1 if p1 else p2_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                slow = head\n",
    "                while slow != fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                return slow\n",
    "        return None\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        fast = slow = head\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                a = slow\n",
    "                b = head\n",
    "                while a != b:\n",
    "                    a=a.next\n",
    "                    b=b.next\n",
    "                return a\n",
    "\n",
    "        \n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return \n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return \n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 快慢指针监测是否有环\n",
    "        # 有环则返回环中一个节点\n",
    "        if not head:\n",
    "            return None\n",
    "        s = head\n",
    "        f = head.next\n",
    "        \n",
    "        while(f):\n",
    "            if f==s:\n",
    "                break\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "            if f:\n",
    "                f = f.next\n",
    "        # 如果有环\n",
    "        if f:\n",
    "            # 在f下一个节点处将链表拆开，问题转化为求俩链表相交节点\n",
    "            sh = f.next\n",
    "            f.next = None\n",
    "            \n",
    "            fh = head\n",
    "            fi,si = fh,sh\n",
    "            while True:\n",
    "                if fi==si:\n",
    "                    break\n",
    "                fi = fi.next\n",
    "                if not fi:\n",
    "                    fi = sh\n",
    "                si = si.next\n",
    "                if not si:\n",
    "                    si = fh\n",
    "            return fi\n",
    "                \n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        hashSet = dict()\n",
    "        while head:\n",
    "            if head in hashSet:\n",
    "                return head\n",
    "            else:\n",
    "                hashSet[head] = 1\n",
    "                head = head.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        appear = set()\n",
    "        while head:\n",
    "            if head not in appear: \n",
    "                appear.add(head)\n",
    "                head = head.next\n",
    "            else: return head\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s =set()\n",
    "        p=head\n",
    "        while p:\n",
    "            if p in s:\n",
    "                return p\n",
    "            s.add(p)\n",
    "            p=p.next\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        head_set = set()\n",
    "        while head:\n",
    "            if head in head_set:\n",
    "                return head\n",
    "            head_set.add(head)\n",
    "            head = head.next\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        a = head\n",
    "        while a not in s and a != None:\n",
    "            s.add(a)\n",
    "            a = a.next\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        node_list = set()\n",
    "        while head:\n",
    "            if head in node_list:\n",
    "                return head\n",
    "            else:\n",
    "                node_list.add(head)\n",
    "                head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        while head:\n",
    "            if head in s:\n",
    "                return head\n",
    "            s.add(head)\n",
    "            head = head.next\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        seen=set()\n",
    "        while head:\n",
    "            if head in seen:\n",
    "                return head\n",
    "            seen.add(head)\n",
    "            head=head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        h = set()\n",
    "        while head and head not in h:\n",
    "            h.add(head)\n",
    "            head = head.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "    \n",
    "        while head:\n",
    "            if head in s:\n",
    "                return head\n",
    "            s.add(head)\n",
    "            head = head.next\n",
    "            \n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        while head:\n",
    "            if head in s:\n",
    "                return head\n",
    "            s.add(head)\n",
    "            head = head.next\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        hashSet=set()\n",
    "        while head:\n",
    "            if head in hashSet:\n",
    "                return head\n",
    "            else:\n",
    "                hashSet.add(head)\n",
    "                head=head.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        while head:\n",
    "            if isinstance(head.val, bool):\n",
    "                return head\n",
    "            else:\n",
    "                head.val = True\n",
    "                head = head.next\n",
    "        \n",
    "        return None\n",
    "        # if head == None:\n",
    "        #     return None\n",
    "        # pos = head\n",
    "        # tval = {head.val}\n",
    "        # # tval = pos.val\n",
    "        # while pos.next:\n",
    "        #     pos = pos.next\n",
    "        #     if pos.val in tval:\n",
    "        #         print('hhh')\n",
    "        #         return pos\n",
    "        #     tval.add(pos.val)\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        hash_map={}\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur in hash_map:\n",
    "                return cur\n",
    "            hash_map[cur]=0\n",
    "            cur=cur.next\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        p,res=head,{}\n",
    "        while p:\n",
    "            if p in res:return p\n",
    "            res[p]=0\n",
    "            p=p.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        meet = set()\n",
    "        while head:\n",
    "            if head in meet:\n",
    "                return head\n",
    "            meet.add(head)\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        nodeset=set()\n",
    "        temphead=head\n",
    "        while temphead:\n",
    "            if temphead in nodeset:\n",
    "                return temphead\n",
    "            else:\n",
    "                nodeset.add(temphead)\n",
    "                temphead=temphead.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        while head:\n",
    "            if type(head.val) == list:\n",
    "                head.val = head.val[0]\n",
    "                return head\n",
    "            else:\n",
    "                head.val = [head.val, 1]\n",
    "                head = head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        while not head or not head.next:\n",
    "            return None\n",
    "        slow = head.next\n",
    "        fast = slow.next\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        if fast != slow:\n",
    "            return\n",
    "        \n",
    "        slow = head\n",
    "        while fast != slow:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "            if fast == slow:\n",
    "                break\n",
    "\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return fast\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        ret = None\n",
    "\n",
    "        _list = []\n",
    "        node = head\n",
    "        while node != None:\n",
    "            if node in _list:\n",
    "                ret = node\n",
    "                break\n",
    "            else:\n",
    "                _list.append(node)\n",
    "                node = node.next\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        # 使用快慢指针进行环路检测\n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "            # 如果快慢指针相遇，说明存在环路\n",
    "            if slow == fast:\n",
    "                break\n",
    "        else:\n",
    "            return None  # 如果快指针到达链表尾部，则无环\n",
    "\n",
    "        # 寻找环路开始节点\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        return slow  # 返回环路开始节点\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            if not fast.next:\n",
    "                return None\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                p = head\n",
    "                while p != slow:\n",
    "                    p = p.next\n",
    "                    slow = slow.next\n",
    "                return p\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None:\n",
    "            return None\n",
    "        stk=[]\n",
    "        while head:\n",
    "            if head not in stk:\n",
    "                stk.append(head)\n",
    "            else:\n",
    "                return head\n",
    "            head=head.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            if fast.next is None:\n",
    "                return None\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                curr = head\n",
    "                while curr != slow:\n",
    "                    curr = curr.next\n",
    "                    slow = slow.next\n",
    "                return curr\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        f = head\n",
    "        s = head\n",
    "        \n",
    "        while(s and s.next):\n",
    "            s = s.next\n",
    "            if not f.next:\n",
    "                return None\n",
    "            f = f.next.next\n",
    "            if not f:\n",
    "                return None\n",
    "            if f == s:\n",
    "                # 说明有环\n",
    "                break\n",
    "        if not s or not s.next:\n",
    "            return None\n",
    "        \n",
    "        s = head\n",
    "        while (s != f):\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "        return s\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                cur = head\n",
    "                while cur != slow:\n",
    "                    cur = cur.next\n",
    "                    slow = slow.next\n",
    "                return slow\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next: return None\n",
    "        f, s = head, head\n",
    "        while f and f.next:\n",
    "            s = s.next\n",
    "            f = f.next.next\n",
    "            if f == s:\n",
    "                p = head\n",
    "                while p != s:\n",
    "                    p = p.next\n",
    "                    s = s.next\n",
    "                return p\n",
    "        return None\n",
    "\n",
    "\n",
    "'''\n",
    "a + b \n",
    "a + (n + 1)b + nc\n",
    "2a + 2b = a + (n + 1)b + nc\n",
    "a = (n - 1)b + nc\n",
    "a = nb + nc - b\n",
    "a = c + (n - 1)(b + c)\n",
    "'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next: #开始走位\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast: # 相遇\n",
    "                break\n",
    "            \n",
    "        # 若无相会处，则无环路\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        # 若两者以相同的速度移动，则必然在环路起始处相遇\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next: #开始走位\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast: # 相遇\n",
    "                break\n",
    "            \n",
    "        # 若无相会处，则无环路\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        # 若两者以相同的速度移动，则必然在环路起始处相遇\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                fast = head\n",
    "                while fast != slow:\n",
    "                    fast = fast.next\n",
    "                    slow = slow.next\n",
    "                return slow\n",
    "        return None\n",
    "        \n",
    "        # while slow.next and fast.next and fast.next.next:\n",
    "        #     fast = fast.next.next\n",
    "        #     slow = slow.next\n",
    "        #     if slow == fast:\n",
    "        #         fast = head\n",
    "        #         while slow and fast:\n",
    "        #             if slow == fast:\n",
    "        #                 return slow\n",
    "        #             slow = slow.next\n",
    "        #             fast = fast.next\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return None\n",
    "        \n",
    "        slow = fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        if fast != slow:\n",
    "            return None\n",
    "\n",
    "        pre = head\n",
    "        while pre != slow:\n",
    "            pre = pre.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return pre\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast !=None and fast.next!=None:\n",
    "            fast = fast.next.next\n",
    "            slow= slow.next \n",
    "            if fast==slow:\n",
    "                break\n",
    "        if fast!=slow:\n",
    "            return None\n",
    "        ptr = head\n",
    "        while ptr!=None and ptr.next!=None:\n",
    "            if ptr == slow:\n",
    "                return ptr\n",
    "            ptr = ptr.next\n",
    "            slow= slow.next\n",
    "            \n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast:\n",
    "            if not fast or not fast.next:\n",
    "                return None\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:  # 相遇第一次\n",
    "                p = head\n",
    "                while p != slow:\n",
    "                    slow = slow.next\n",
    "                    p = p.next\n",
    "                if p == slow:\n",
    "                    return p\n",
    "        return None\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        if not fast or not fast.next:\n",
    "            return\n",
    "        cur = head\n",
    "        while cur != slow:\n",
    "            cur = cur.next\n",
    "            slow = slow.next\n",
    "        return cur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 快慢指针:无环的话，快指针达到终点，有环，快慢指针重合时，快指针从头开始，下一次重合的结点\n",
    "        fast,slow = head,head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if  fast == slow:\n",
    "                break\n",
    "        if fast == None or fast.next == None:\n",
    "            return None\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next: #开始走位\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast: # 相遇\n",
    "                break\n",
    "            \n",
    "        # 若无相会处，则无环路\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        # 若两者以相同的速度移动，则必然在环路起始处相遇\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None \n",
    "        slow, fast, flag = head, head, False\n",
    "        while fast and fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                flag = True\n",
    "                break\n",
    "        if not flag:\n",
    "            return None \n",
    "        cur1, cur2 = head, slow\n",
    "        while cur1 != cur2:\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        return cur1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                slow = head\n",
    "                while slow != fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                return slow\n",
    "        return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        s, f = head, head\n",
    "        while f and f.next:\n",
    "\n",
    "            s = s.next\n",
    "            f = f.next.next\n",
    "            if f == s:\n",
    "                break\n",
    "        if not f or not f.next:\n",
    "            return None\n",
    "        s = head\n",
    "        while s != f:\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        p = head\n",
    "        while p != None:\n",
    "            if p.val == None:\n",
    "                return p\n",
    "            p.val = None\n",
    "            p = p.next\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        hash_map = dict()\n",
    "        while head:\n",
    "            if head not in hash_map:\n",
    "                hash_map[head] = 1\n",
    "                head = head.next\n",
    "            else:\n",
    "                return head\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        appeared = []\n",
    "        index = 0\n",
    "        while head:\n",
    "            if head in appeared:\n",
    "                return head\n",
    "            appeared.append(head)\n",
    "            head = head.next\n",
    "        return None\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast=slow=head\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            if slow==fast:\n",
    "                slow=head\n",
    "                while slow!=fast:\n",
    "                    slow=slow.next\n",
    "                    fast=fast.next\n",
    "                return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if slow is fast:break\n",
    "        if not fast or not fast.next:\n",
    "            return\n",
    "        fast = head\n",
    "        while fast is not slow:\n",
    "            fast =  fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast=slow=head\n",
    "        while fast and fast.next:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "            if fast==slow:\n",
    "                fast=head\n",
    "                while fast!=slow:\n",
    "                    fast=fast.next\n",
    "                    slow=slow.next\n",
    "                return slow\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            fast = fast.next if fast else None\n",
    "            slow = slow.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        if fast:\n",
    "            fast = head\n",
    "            while slow != fast:\n",
    "                fast = fast.next\n",
    "                slow = slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        slow = head\n",
    "        fast = head\n",
    "        # 链表长度只有2的情况\n",
    "        if fast.next and fast.next.next == slow:\n",
    "            return head\n",
    "        while fast.next is not None and fast.next.next is not None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            # 说明环路存在\n",
    "            if slow == fast:\n",
    "                ptr = head\n",
    "                while ptr != slow:\n",
    "                    ptr = ptr.next\n",
    "                    slow = slow.next\n",
    "                return ptr\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow,fast = head, head \n",
    "        while fast and fast.next:\n",
    "            slow = slow.next \n",
    "            fast = fast.next.next \n",
    "            if slow ==fast:\n",
    "                break \n",
    "        if not fast or not fast.next: \n",
    "            return None \n",
    "        slow = head \n",
    "        while slow != fast:\n",
    "            slow = slow.next \n",
    "            fast = fast.next \n",
    "        return slow "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        node_record = set()\n",
    "        node = head\n",
    "        while node:\n",
    "            if node in node_record:\n",
    "                return node\n",
    "            else:\n",
    "                node_record.add(node)\n",
    "                node = node.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = head    #慢指针\n",
    "        quick = head  # 快指针\n",
    "\n",
    "        while quick != None:\n",
    "            slow = slow.next\n",
    "            if quick.next == None:\n",
    "                return None\n",
    "            quick = quick.next.next\n",
    "            if quick == slow :\n",
    "                while slow != head :\n",
    "                    slow = slow.next\n",
    "                    head = head.next\n",
    "                return slow\n",
    "\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "        slow, fast = head, head\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            if not fast.next:\n",
    "                return None\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                res = head\n",
    "                while slow != res:\n",
    "                    slow = slow.next\n",
    "                    res = res.next\n",
    "                return res\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        vis=set([head])\n",
    "        while head and head.next:\n",
    "            head=head.next\n",
    "            if head in vis:\n",
    "                return head\n",
    "            vis.add(head)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next: #开始走位\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast: # 相遇\n",
    "                break\n",
    "            \n",
    "        # 若无相会处，则无环路\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        # 若两者以相同的速度移动，则必然在环路起始处相遇\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow\n",
    "()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        nodeSet = set()\n",
    "        while head and head not in nodeSet:\n",
    "            nodeSet.add(head)\n",
    "            head = head.next\n",
    "        return head if head else None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        node_set = set()\n",
    "        while head:\n",
    "            if head in node_set:\n",
    "                return head\n",
    "            node_set.add(head)\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode):\n",
    "        if head == None:\n",
    "            return None\n",
    "        # 获取是否存在的有两个指向的节点\n",
    "        hash = {head:0}\n",
    "        # 将所有节点存入字典中\n",
    "        i = 1\n",
    "        while head.next:\n",
    "            if head.next in hash.keys():\n",
    "                return head.next\n",
    "                break\n",
    "            else:\n",
    "                hash[head.next] = i\n",
    "                head = head.next\n",
    "                i += 1\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        node_set = set()\n",
    "\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            if cur not in node_set:\n",
    "                node_set.add(cur)\n",
    "            else:\n",
    "                return cur\n",
    "            cur = cur.next\n",
    "        \n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:   return None\n",
    "        node_dic = {}\n",
    "        counter = 0\n",
    "        while head != None:\n",
    "            if head in node_dic:    return head\n",
    "            node_dic[head] = counter\n",
    "            counter += 1\n",
    "            head = head.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        recorder = set()\n",
    "        while cur:\n",
    "            recorder.add(cur)\n",
    "            if cur.next in recorder:\n",
    "                return cur.next\n",
    "            cur = cur.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        node_record = set()\n",
    "        node = head\n",
    "        while node:\n",
    "            if node in node_record:\n",
    "                return node\n",
    "            else:\n",
    "                node_record.add(node)\n",
    "                node = node.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        graph_degree = set()\n",
    "        p = head\n",
    "        while p:\n",
    "            if p in graph_degree:\n",
    "                return p\n",
    "            else:\n",
    "                graph_degree.add(p)\n",
    "                p = p.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        recorder = set()\n",
    "        while cur:\n",
    "            recorder.add(cur)\n",
    "            if cur.next in recorder:\n",
    "                return cur.next\n",
    "            cur = cur.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        nodes = set()\n",
    "        while head:\n",
    "            if head not in nodes:\n",
    "                nodes.add(head)\n",
    "            else:\n",
    "                return head\n",
    "            head = head.next\n",
    "        \n",
    "        return None"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
